#include <iostream>
#include <vector>
#include <cstdlib>       // for srand and rand
#include <ctime>        // for time
#include <algorithm>    // for sort
using namespace std;

/*
* 二分查找算法
*/

#define ElemType int
#define ElemNum 10

int BinarySearch(const vector<ElemType>& nums, ElemType target) {
    int left = 0;
    int right = nums.size() - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2; // 防止溢出

        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] < target) {
            left = mid + 1;
        }
    }

    return -1;
}

void Print(const vector<ElemType>& arr) {
    for (const ElemType& elem : arr) {
        cout << elem << " ";
    }
    cout << endl << endl;
}

int main(void) {
    // 设置随机数种子
    srand(time(0));

    // 随机生成测试用例
    vector<ElemType> arr(ElemNum);
    for (int i = 0; i < ElemNum; ++i) {
        arr[i] = rand() % 100 + 1; // 随机生成 1~100 随机数
    }
    sort(arr.begin(), arr.end()); // 二分查找算法只适用于有序数组

    cout << "原始数组：" << endl;
    Print(arr);
    
    ElemType target = arr[rand()%arr.size()];
    cout << "要查找的元素为：" << target << endl;
    int res = BinarySearch(arr, target);

    if (res != -1) {
        cout << "查找成功" << endl;
    } else {
        cout << "查找失败" << endl;
    }

    return 0;
}